{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Pow(x, n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #recursion #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #递归 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: myPow"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #Pow(x, n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>实现&nbsp;<a href=\"https://www.cplusplus.com/reference/valarray/pow/\">pow(<em>x</em>,&nbsp;<em>n</em>)</a>&nbsp;，即计算 x 的 n 次幂函数（即，x<sup>n</sup>）。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>x = 2.00000, n = 10\n",
    "<strong>输出：</strong>1024.00000\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>x = 2.10000, n = 3\n",
    "<strong>输出：</strong>9.26100</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>x = 2.00000, n = -2\n",
    "<strong>输出：</strong>0.25000\n",
    "<strong>解释：</strong>2<sup>-2</sup> = 1/2<sup>2</sup> = 1/4 = 0.25</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>-100.0 &lt;&nbsp;x&nbsp;&lt; 100.0</code></li>\n",
    "\t<li><code>-2<sup>31</sup>&nbsp;&lt;= n &lt;=&nbsp;2<sup>31</sup>-1</code></li>\n",
    "\t<li><code>-10<sup>4</sup>&nbsp;&lt;= x<sup>n</sup>&nbsp;&lt;= 10<sup>4</sup></code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p>注意：本题与主站 50 题相同：<a href=\"https://leetcode-cn.com/problems/powx-n/\">https://leetcode-cn.com/problems/powx-n/</a></p>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [shu-zhi-de-zheng-shu-ci-fang-lcof](https://leetcode.cn/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [shu-zhi-de-zheng-shu-ci-fang-lcof](https://leetcode.cn/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['2.00000\\n10', '2.10000\\n3', '2.00000\\n-2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNonZeroProduct(self, p: int) -> int:\n",
    "        def myPow(x, n):\n",
    "            ans = 1\n",
    "            while n > 0:\n",
    "                if n % 2 == 1:\n",
    "                    ans = (ans * x) % MOD\n",
    "                x = x * x % MOD\n",
    "                n //= 2\n",
    "            return ans\n",
    "\n",
    "        if p == 1:  return 1\n",
    "        MOD = 10 ** 9 + 7\n",
    "        ans = myPow(((1 << p) - 2), (((1 << p) - 2) // 2)) \n",
    "        return (ans * ((1 << p) - 1)) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNonZeroProduct(self, p: int) -> int:\n",
    "        def myPow(x, n):\n",
    "            ans = 1\n",
    "            while n > 0:\n",
    "                if n % 2 == 1:\n",
    "                    ans = (ans * x) % MOD\n",
    "                x = x * x % MOD\n",
    "                n //= 2\n",
    "            return ans\n",
    "\n",
    "        if p == 1:  return 1\n",
    "        MOD = 10 ** 9 + 7\n",
    "        ans = myPow(((1 << p) - 2), (((1 << p) - 2) // 2)) \n",
    "        return (ans * ((1 << p) - 1)) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        if n < 0:\n",
    "            x = 1 / x\n",
    "            n = -n\n",
    "\n",
    "        result = 1\n",
    "        while n > 0:\n",
    "            if n % 2 == 1:\n",
    "                result *= x\n",
    "            x *= x\n",
    "            n //= 2\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        if x == 0: return 0\n",
    "        res = 1\n",
    "        if n < 0: x, n = 1/ x , -n \n",
    "        while n:\n",
    "            if n & 1: \n",
    "                res *= x \n",
    "            x *= x  \n",
    "            n >>= 1\n",
    "        return res   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        if x==0:return 0\n",
    "        res = 1\n",
    "        if n<0:\n",
    "            x,n = 1/x,-n\n",
    "        while n:\n",
    "            if n&1:res*=x\n",
    "            x*=x\n",
    "            n>>=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        if n < 0:\n",
    "            return 1 / self.myPow(x, -n)\n",
    "        # print(x, n)\n",
    "        if n == 0:\n",
    "            return 1.\n",
    "        if n == 1:\n",
    "            return x\n",
    "        if n % 2 == 1:\n",
    "            res = x\n",
    "        else:\n",
    "            res = 1\n",
    "        sub_val = self.myPow(x, n // 2)\n",
    "        return res * sub_val * sub_val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x, n):\n",
    "        if n == 0:\n",
    "            return 1\n",
    "        if n < 0:\n",
    "            x = 1 / x\n",
    "            n = -n\n",
    "        return self.powHelper(x, n)\n",
    "\n",
    "    def powHelper(self, x, n):\n",
    "        if n == 1:\n",
    "            return x\n",
    "        half = self.powHelper(x, n // 2)\n",
    "        if n % 2 == 0:\n",
    "            return half * half\n",
    "        else:\n",
    "            return half * half * x\n",
    "# 创建 Solution 类的实例\n",
    "solution = Solution()\n",
    "\n",
    "# 定义 x 和 n\n",
    "x = 2.0\n",
    "n = 10\n",
    "\n",
    "# 调用 myPow 方法\n",
    "result = solution.myPow(x, n)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        if x == 0: return 0\n",
    "        if n == 0: return 1\n",
    "        \n",
    "        if n<0: x,n = 1/x,-n\n",
    "        \n",
    "        rt = 1\n",
    "        now = x\n",
    "        while n>0:\n",
    "            if n%2 == 1:\n",
    "                rt = rt*now\n",
    "            n = n//2\n",
    "            now = now*now\n",
    "\n",
    "\n",
    "        \n",
    "        return rt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        if n < 0:\n",
    "            x = 1/x\n",
    "            n = -n\n",
    "        res = 1\n",
    "        while n != 0:\n",
    "            if n &1 == 1:\n",
    "                res = res * x\n",
    "            x *= x\n",
    "            n = n>>1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        if x == 0: return 0\n",
    "        res = 1\n",
    "        if n < 0 :\n",
    "            x = 1 / x\n",
    "            n = -n\n",
    "        \n",
    "        while n:\n",
    "            if n & 1:\n",
    "                res *= x\n",
    "            x *= x\n",
    "            n >>= 1\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        res = 1\n",
    "        if n < 0:\n",
    "            n *= -1\n",
    "            x = 1 / x\n",
    "        while n > 0:\n",
    "            if n & 1:\n",
    "                res *= x\n",
    "            x *= x\n",
    "            n >>= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        if x == 0: \n",
    "            return 0\n",
    "        res = 1\n",
    "        if n < 0: \n",
    "            x, n = 1 / x, -n\n",
    "        while n:\n",
    "            if n & 1: res *= x\n",
    "            x *= x\n",
    "            n >>= 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        return pow(x, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        if x == 0: return 0\n",
    "        x, n = (x, n) if n > 0 else (1/x, -n)\n",
    "        res = 1\n",
    "        while n:\n",
    "            if n & 1:\n",
    "                res *= x\n",
    "            x *= x\n",
    "            n >>= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        def qucikMul(N):\n",
    "            ans = 1\n",
    "            x_1 = x\n",
    "            \n",
    "            while N > 0:\n",
    "                if N % 2 == 1:\n",
    "                    ans *= x_1\n",
    "                x_1 *= x_1\n",
    "                N //= 2\n",
    "            return ans \n",
    "        return qucikMul(n) if n >= 0 else 1/qucikMul(-n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        res = 1\n",
    "        if n < 0:\n",
    "            n = -n\n",
    "            x = 1/x\n",
    "\n",
    "        while n > 0:\n",
    "            if n % 2 == 1:\n",
    "                res = res * x\n",
    "                n = n - 1\n",
    "            x = x * x\n",
    "            n = n / 2\n",
    "        \n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        if x==0.0:return 0.0\n",
    "        if n==0:return 1\n",
    "        if n<0:\n",
    "            n,x=-n,1/x\n",
    "        res = 1\n",
    "        while n > 1:\n",
    "            if n%2==1:res *=x\n",
    "            x *=x\n",
    "            n = n//2\n",
    "        res *=x\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def quickMul(self, x, n):\n",
    "        ans = 1.0\n",
    "        x_contribute = x\n",
    "        while n:\n",
    "            if n % 2 == 1:\n",
    "                ans *= x_contribute\n",
    "            x_contribute *= x_contribute\n",
    "            n //= 2\n",
    "        return ans\n",
    "\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        return self.quickMul(x, n) if n >= 0 else 1.0 / (self.quickMul(x, -n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        return x**n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        if n < 0:\n",
    "            _n = -n\n",
    "        else:\n",
    "            _n = n\n",
    "        ans = 1\n",
    "        for _ in range(32):\n",
    "            if _n & 1:\n",
    "                ans = ans * x\n",
    "            x = x * x\n",
    "            _n = _n >> 1\n",
    "        return ans if n > 0 else (1 / ans)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        if x == 0.0:\n",
    "            return 0.0\n",
    "        if n < 0:\n",
    "            x = 1 / x\n",
    "            n = -n\n",
    "        res = 1\n",
    "        while n:\n",
    "            if n & 1:\n",
    "                res *= x\n",
    "            x *= x\n",
    "            n >>= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        res = float(1)\n",
    "        if n < 0:\n",
    "            n = -n\n",
    "            x = 1 / x\n",
    "        while n > 0:\n",
    "            if n % 2 > 0:\n",
    "                res = res * x\n",
    "            x *= x\n",
    "            n //= 2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        if x == 0:\n",
    "            return 0\n",
    "        res = 1\n",
    "        if n < 0:\n",
    "            x = 1 / x\n",
    "            n = -n\n",
    "        while n:\n",
    "            if n & 1:\n",
    "                res *= x\n",
    "            x *= x\n",
    "            n >>= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "#            if n > 0:\n",
    "#                x_initial = x\n",
    "#                while n != 1:\n",
    "#                    x *= x_initial\n",
    "#                    n -= 1\n",
    "#            elif n == 0:\n",
    "#                return 1\n",
    "#            elif n < 0:\n",
    "#                n = -n\n",
    "#                x = 1/x\n",
    "#                x_initial = x\n",
    "#                while n != 1:\n",
    "#                    x *= x_initial\n",
    "#                    n -= 1\n",
    "#            return x\n",
    "        def quickMul(N):\n",
    "            if N == 0:\n",
    "                return 1.0\n",
    "            x_rep = quickMul(N // 2)\n",
    "            if N % 2 == 0:\n",
    "                return x_rep*x_rep\n",
    "            else:\n",
    "                return  x_rep * x_rep * x\n",
    "\n",
    "        return quickMul(n) if n >= 0 else 1.0/quickMul(-n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        if x == 0:\n",
    "            return 0\n",
    "        if n == 0:\n",
    "            return 1 \n",
    "        res = 1\n",
    "        if n < 0:\n",
    "            x, n = 1/x, -n \n",
    "        while n:\n",
    "            if n & 1 == 1:\n",
    "                res *= x\n",
    "            x *= x\n",
    "            n >>= 1\n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        return x**n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        if x==0.0:\n",
    "            return 0.0\n",
    "        \n",
    "        if n<0:\n",
    "            x,n = 1/x,-n\n",
    "        \n",
    "        res = 1\n",
    "        \n",
    "        while(n):\n",
    "            if (n&1):\n",
    "                res *= x\n",
    "            x *= x\n",
    "            n >>=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        if n == 0:\n",
    "            return 1\n",
    "        if x == 0:\n",
    "            return 0\n",
    "        if n<0:\n",
    "            x,n=1/x,-n\n",
    "        res = 1\n",
    "        while n:\n",
    "            if n&1:\n",
    "                res = res*x\n",
    "            x = x*x\n",
    "            n>>=1\n",
    "        return res\n",
    "        \n",
    "    \n",
    " \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        # 快速幂\n",
    "        res = 1\n",
    "        if n < 0:\n",
    "            a = -n\n",
    "            while a > 0:\n",
    "                if a % 2 == 1:\n",
    "                    res = res * x\n",
    "                x = x * x\n",
    "                a = a // 2\n",
    "            return 1/res\n",
    "        \n",
    "        if n == 0:\n",
    "            return 1\n",
    "\n",
    "        while n > 0:\n",
    "            if n % 2 == 1:\n",
    "                res = res * x\n",
    "            x = x * x\n",
    "            n = n // 2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        return self.dfs(x, n) if n >= 0 else 1.0 / self.dfs(x, -n)\n",
    "\n",
    "    def dfs(self, x, n):\n",
    "        if n == 0:\n",
    "            return 1.0\n",
    "        y = self.dfs(x, n // 2)\n",
    "        return y * y if n % 2 == 0 else y * y * x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def quickMul(self, x, n):\n",
    "        if n == 0:\n",
    "            return 1.0\n",
    "        y = self.quickMul(x, n // 2)\n",
    "        return y * y if n % 2 == 0 else y * y *x\n",
    "\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        return self.quickMul(x, n) if n >= 0 else 1.0 / (self.quickMul(x, -n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        if x == 0:\n",
    "            return 0\n",
    "        if n == 0:\n",
    "            return 1 \n",
    "        if n < 0:\n",
    "            x, n = 1/x, -n\n",
    "        res = 1\n",
    "        while n:\n",
    "            if n & 1 == 1:\n",
    "                res *= x \n",
    "            x *= x \n",
    "            n >>= 1\n",
    "        return res \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        def quickMul(N):\n",
    "            ans = 1.0\n",
    "            x_contribute = x\n",
    "            while N > 0:\n",
    "                if N % 2 == 1:\n",
    "                    ans *= x_contribute\n",
    "                x_contribute *= x_contribute\n",
    "                N //= 2\n",
    "            return ans\n",
    "        \n",
    "        return quickMul(n) if n >= 0 else 1.0 / quickMul(-n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        if n < 0:\n",
    "            return self.myPow(1/x, -n)\n",
    "        elif n == 0:\n",
    "            return 1\n",
    "        # elif n == 1:\n",
    "        #     return x\n",
    "        else:\n",
    "            return self.myPow(x*x, n//2) * (x if n%2 else 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        if x == 0:\n",
    "            return 0\n",
    "\n",
    "        if n == 0:\n",
    "            return 1\n",
    "        if n < 0:\n",
    "            x, n = 1/x, -n\n",
    "        res = 1\n",
    "        while n:\n",
    "            if n & 1 == 1:\n",
    "                res *= x\n",
    "            x *= x\n",
    "            n >>= 1\n",
    "        return res\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        # if n == 0:\n",
    "        #     return 1\n",
    "        # elif n < 0:\n",
    "        #     return self.myPow(1/x, -n)\n",
    "        # else:\n",
    "        #     return self.myPow(x*x, n//2) * (x if n%2 else 1)\n",
    "\n",
    "        if n < 0:\n",
    "            return self.myPow(1/x, -n)\n",
    "        res = 1\n",
    "        while n:\n",
    "            if n%2:\n",
    "                res *= x\n",
    "            x *= x\n",
    "            n >>= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        # if n==0:return 1\n",
    "        # if n<0:return self.myPow(1/x,-n)\n",
    "        # y=self.myPow(x,abs(n)//2)\n",
    "        # if n%2==1:\n",
    "        #     return y*y*x# if n>0 else 1/(y*y*x)\n",
    "        # else:\n",
    "        #     return y*y# if n>0 else 1/(y*y)\n",
    "        if x == 0.0: return 0.0\n",
    "        res = 1\n",
    "        if n < 0: x, n = 1 / x, -n\n",
    "        while n:\n",
    "            if n & 1: res *= x\n",
    "            x *= x\n",
    "            n >>= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        def quicknum(N):\n",
    "            if N == 0:\n",
    "                return 1\n",
    "            y = quicknum(N//2)\n",
    "            return y*y if N%2 == 0 else y*y*x\n",
    "        return quicknum(n) if n > 0 else 1/quicknum(-n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        neg = n < 0\n",
    "        n = abs(n)\n",
    "        ans = 1.0\n",
    "        while n > 0:\n",
    "            if n % 2:\n",
    "                ans *= x\n",
    "            x *= x\n",
    "            n //= 2\n",
    "        \n",
    "        return ans if not neg else 1.0 / ans\n",
    "\n",
    "        \n",
    "        # @cache\n",
    "        # def f(a, b):\n",
    "        #     if b == 0:\n",
    "        #         return 1.0\n",
    "        #     y = f(a, b // 2)\n",
    "        #     return y * y if b % 2 == 0 else y * y * a\n",
    "        \n",
    "        # return f(x, n) if n >= 0 else 1.0 / f(x, -n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        if n == 0:return 1\n",
    "        res = 1\n",
    "        if n<0:\n",
    "            x = 1/x\n",
    "            n = -n\n",
    "        while n:\n",
    "            if n & 1:res *=x\n",
    "            x*=x\n",
    "            n >>= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:                \n",
    "        if n == 0:return 1        \n",
    "        if n == 1:return x\n",
    "        if n == -1:return 1 / x\n",
    "\n",
    "        if n % 2 != 0:return x * self.myPow(x,n-1)\n",
    "        return self.myPow(x * x,n // 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        if x == 0.0: return 0.0\n",
    "        res = 1\n",
    "        if n < 0: x, n = 1 / x, -n\n",
    "        while n:\n",
    "            if n & 1: res *= x\n",
    "            x *= x\n",
    "            n >>= 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        if x == 0:\n",
    "            return 0\n",
    "        res = 1\n",
    "        if n < 0: x, n = 1 / x, -n\n",
    "        while n:\n",
    "            if n % 2 == 1:\n",
    "                res *= x\n",
    "            x *= x\n",
    "            n >>= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        if x == 0:\n",
    "            return 0\n",
    "        res = 1\n",
    "        if n < 0:\n",
    "            x, n = 1 / x, -n\n",
    "        while n:\n",
    "            if n & 1:\n",
    "                res *= x\n",
    "            x *= x\n",
    "            n >>= 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        if x==0.0 :return 0.0\n",
    "        res = 1\n",
    "        if n<0:x,n = 1/x,-n\n",
    "        while n:\n",
    "            if n%2 == 1:\n",
    "                res *= x\n",
    "            x*=x\n",
    "            n>>=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        return x**n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        if x == 0:\n",
    "            return 0\n",
    "        if n == 0:\n",
    "            return 1\n",
    "        res = 1\n",
    "        if n < 0:\n",
    "            x, n = 1/x, -n\n",
    "        while n:\n",
    "            if n & 1 == 1:\n",
    "                res *= x\n",
    "            x *= x\n",
    "            n >>= 1\n",
    "        return res\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        if n < 0:\n",
    "            x = 1 / x\n",
    "            n = - n\n",
    "        res = 1\n",
    "        while n:\n",
    "            if n & 1:\n",
    "                res *= x\n",
    "            n >>= 1\n",
    "            x *= x\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        if x == 0.0: return 0.0\n",
    "        res = 1\n",
    "        if n < 0: x, n = 1 / x, -n\n",
    "        while (n):\n",
    "            if (n % 2 == 1):\n",
    "                res = res * x\n",
    "            x = x * x\n",
    "            n = n // 2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        return x**n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        return math.pow(x,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        # x=0.0 的幂运算都为0.0\n",
    "        if x==0.0: return 0.0\n",
    "        # 利用res记录最终的结果\n",
    "        res = 1\n",
    "        # 当n为负数时\n",
    "        if n<0 : x, n = 1/x, -n\n",
    "        while n:\n",
    "            if n&1: res*=x\n",
    "            x*=x\n",
    "            n>>=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        if x == 0.0: return 0.0\n",
    "        res = 1\n",
    "        if n < 0: x, n = 1 / x, -n\n",
    "        while (n):\n",
    "            if (n % 2 == 1):\n",
    "                res = res * x\n",
    "            x *= x\n",
    "            n >>= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        if x==0.0:return 0.0\n",
    "        res=1\n",
    "        if n<0:x,n=1/x,-n\n",
    "        while n:\n",
    "            if n&1:res*=x\n",
    "            x*=x\n",
    "            n>>=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        return x ** n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        if x == 0.0: return 0.0\n",
    "        res = 1\n",
    "        if n < 0: x, n = 1 / x, -n\n",
    "        while n:\n",
    "            if n & 1: res *= x\n",
    "            x *= x\n",
    "            n >>= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        # 边界条件、特殊情况\n",
    "        # 递归实现\n",
    "        if n == 0:\n",
    "            return 1.0\n",
    "        if x == 0.0:\n",
    "            return 0.0\n",
    "        if n < 0:\n",
    "            x = 1.0 / x\n",
    "            n = -n\n",
    "        def Power(base, exponent):\n",
    "            if exponent == 0:\n",
    "                return 1\n",
    "            if exponent == 1:\n",
    "                return base\n",
    "            \n",
    "            res = Power(base, exponent >> 1)\n",
    "            res *= res\n",
    "            if exponent & 1:\n",
    "                res *= base\n",
    "            return res\n",
    "       \n",
    "        return Power(x, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        return math.pow(x, n)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "\n",
    "        res=1\n",
    "        def dfs(x,n):\n",
    "            \n",
    "            if n>=0:\n",
    "                if n==0:\n",
    "                    return 1\n",
    "                if n==1:\n",
    "                    return x\n",
    "                if n%2==0:\n",
    "                    res=dfs(x,n//2)\n",
    "                    return res*res\n",
    "                else:\n",
    "                    res=dfs(x,n//2)\n",
    "                    return res*res*x\n",
    "            else:\n",
    "                if n==-1:\n",
    "                    return x**(-1)\n",
    "                if n%2==0:\n",
    "                    res=dfs(x,n//2)\n",
    "                    return res*res\n",
    "                else:\n",
    "                    res=dfs(x,n//2+1)\n",
    "                    return res*res*(x**(-1))\n",
    "        \n",
    "        return dfs(x,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        sign = 1 if n > 0 else 0 \n",
    "        n = abs(n)\n",
    "        res = 1 \n",
    "        while n:\n",
    "            if (n & 1) == 1:\n",
    "                res *= x \n",
    "            x *= x \n",
    "            n >>= 1 \n",
    "        return res if sign else 1/res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        def dfs(n):\n",
    "            if n == 0:\n",
    "                return 1.0\n",
    "            y = dfs(n // 2)\n",
    "            return y * y if n % 2 == 0 else y * y * x\n",
    "        \n",
    "        return dfs(n) if n >= 0 else 1.0 / dfs(-n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        if n==0:\n",
    "            return 1\n",
    "        if n<0:\n",
    "            x= 1/x\n",
    "            n=-n\n",
    "        if n % 2:\n",
    "            return x*self.myPow(x,n-1)\n",
    "        return self.myPow(x*x,n/2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        if x == 0.0: return 0.0\n",
    "        res = 1\n",
    "        if n < 0: x, n = 1/x, -n\n",
    "        while n:\n",
    "            if n & 1: res *= x\n",
    "            x *= x\n",
    "            n >>= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        if x == 0.0: return x\n",
    "        if n < 0: x, n = 1/x, -n\n",
    "        res = 1\n",
    "        # 循环计算\n",
    "        while n:\n",
    "            if n % 2 == 1: res *= x\n",
    "            x *= x\n",
    "            n >>= 1  # 相当于n向下整除2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        return pow(x, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        def quickMul(N):\n",
    "            if N == 0:\n",
    "                return 1.0\n",
    "            y = quickMul(N // 2)\n",
    "            return y * y if N % 2 == 0 else y * y * x\n",
    "        \n",
    "        return quickMul(n) if n >= 0 else 1.0 / quickMul(-n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        if x == 0: return 0\n",
    "        r = 1\n",
    "        if n < 0: x, n = 1 / x, -n\n",
    "        while n:\n",
    "            if n & 1: r *= x\n",
    "            x *= x\n",
    "            n >>= 1\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        return x**n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        if n ==0:\n",
    "            return 1\n",
    "        elif n < 0:\n",
    "            return 1 / self.myPow(x, -n)\n",
    "        elif (n % 2) == 0:\n",
    "            res = self.myPow(x, n//2)\n",
    "            return res * res\n",
    "        else:\n",
    "            res = self.myPow(x, n //2)\n",
    "            return res*res*x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        res=1\n",
    "        if x==0:\n",
    "            return 0\n",
    "        if n<0:\n",
    "            x=1/x\n",
    "            n=-n\n",
    "        while n:\n",
    "            if n&1:\n",
    "                res*=x\n",
    "            x*=x\n",
    "            n>>=1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        def quickMul(N):\n",
    "            if N == 0:\n",
    "                return 1.0\n",
    "            y = quickMul(N // 2)\n",
    "            return y * y if N % 2 == 0 else y * y * x\n",
    "        \n",
    "        return quickMul(n) if n >= 0 else 1.0 / quickMul(-n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        if n ==0:\n",
    "            return 1\n",
    "        elif n < 0:\n",
    "            return 1 / self.myPow(x, -n)\n",
    "        elif (n % 2) == 0:\n",
    "            res = self.myPow(x, n//2)\n",
    "            return res * res\n",
    "        else:\n",
    "            res = self.myPow(x, n //2)\n",
    "            return res*res*x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        if n<0:\n",
    "            return self.myPow(1/x,-n)\n",
    "        if n==0:\n",
    "            return 1.0\n",
    "        if n==1:\n",
    "            return x\n",
    "        result=self.myPow(x,n//2)\n",
    "        return result*result if n%2==0 else result*result*x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        if x == 0.0: return 0.0\n",
    "        if n < 0: x, n = 1 / x, -n\n",
    "        res = 1\n",
    "        while n>0:\n",
    "            if n%2==1:\n",
    "                res = res*x\n",
    "            x=x*x\n",
    "            n = n//2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        if x == 0.0:\n",
    "            return 0.0\n",
    "        if n < 0:\n",
    "            x,n = 1/x,-n\n",
    "        res = 1.0\n",
    "        while n:\n",
    "            if n&1 == 1:\n",
    "                res *= x\n",
    "            x *= x\n",
    "            n  = n >> 1\n",
    "        return res\n",
    "\n",
    "    def myPowV1(self, x: float, n: int) -> float:\n",
    "        return x**n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
